# 01. 合并两个有序数组.py
from typing import List  # 导入 List

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        seek_nums1 = m-1  # 指向nums1有效部分的最后一个元素的指针
        seek_nums2 = n-1  # 指向nums2的最后一个元素的指针
        seek_new = n+m-1  # 指向nums1的最后一个元素的指针
        # while seek_new >= 0:  # 错误写法
        while seek_nums1 >= 0 and seek_nums2 >= 0:
            if nums1[seek_nums1] >= nums2[seek_nums2]:
                nums1[seek_new] = nums1[seek_nums1]
                seek_nums1 -= 1
            else:
                nums1[seek_new] = nums2[seek_nums2]
                seek_nums2 -= 1
            seek_new -= 1

        # 若nums2先移动完，则nums1中剩下的元素保留原位置就行
        # 若nums1先移动完，则需要把nums2中剩下的元素移动到nums1中
        if seek_nums1 < 0:
            nums1[:seek_nums2+1] = nums2[:seek_nums2+1]


if __name__ == '__main__':
    solution = Solution()
    nums1 = [1, 2, 3, 0, 0, 0]
    nums2 = [2, 5, 6]
    solution.merge(nums1, 3, nums2, 3)
    print(nums1)